package com.datastructure.picture;

/**
 * @author: 临晖
 * @date: 2023/12/09
 * @description:
 */


import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 *
 * 图
 *
 */
public class Solution {

    /**
     * 797. 所有可能的路径
     * 中等
     * 449
     * 相关企业
     * 给你一个有 n 个节点的 有向无环图（DAG），请你找出所有从节点 0 到节点 n-1 的路径并输出（不要求按特定顺序）
     *  graph[i] 是一个从节点 i 可以访问的所有节点的列表（即从节点 i 到节点 graph[i][j]存在一条有向边）。
     * @param graph
     * @return
     */
    List<List<Integer>> lists = new ArrayList<>();
    List<Integer> list = new ArrayList<>();
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        //思路一
        if (graph.length == 0) {
            return lists;
        }
        list.add(0);
        dfs(graph, 0);
        return lists;
    }


    public void dfs(int[][] graph, int a) {
        //结束条件
        if (graph[a].length == 0 && graph.length - 1 == a) {
            lists.add(new ArrayList<Integer>(list));
        }
        for (int i = 0; i < graph[a].length; i++) {
            list.add(graph[a][i]);
            dfs(graph, graph[a][i]);
            list.remove(list.size() - 1);
        }
    }


    /**
     *
     *200. 岛屿数量
     * 中等
     * 2.4K
     * 相关企业
     * 给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
     * 岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
     * 此外，你可以假设该网格的四条边均被水包围。
     *
     * @param grid
     * @return
     */
    public int numEnclaves(int[][] grid) {
        for(int i = 0; i < grid.length; i++){
            if(grid[i][0] == 1) {
                bfs1(grid, i, 0);
            }
            if(grid[i][grid[0].length - 1] == 1) {
                bfs1(grid, i, grid[0].length - 1);
            }
        }
        //初始化的時候，j 的上下限有調整過，必免重複操作。
        for(int j = 1; j < grid[0].length - 1; j++){
            if(grid[0][j] == 1) {
                bfs1(grid, 0, j);
            }
            if(grid[grid.length - 1][j] == 1) {
                bfs1(grid, grid.length - 1, j);
            }
        }


        int maxArea = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) {
                    maxArea  += bfs1(grid, i, j);
                }
            }
        }
        return maxArea;
    }

    public int bfs1(int[][] grid, int x, int y) {
        if (!inArea(grid, x, y)) {      //如果超出范围
            return 0;
        }

        if (grid[x][y] != 1) {        //如果不为一
            return 0;
        }

        grid[x][y] = 0;     //防止重复

        return 1 + bfs1(grid, x - 1, y) +
        bfs1(grid, x + 1, y) +
        bfs1(grid, x, y + 1) +
        bfs1(grid, x, y - 1);

    }





    /**
     *
     * 130. 被围绕的区域
     * 中等
     * 1.1K
     * 相关企业
     * 给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' ，找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。
     *
     * @param board
     */
    public void solve(char[][] board) {
        //第一步，将边上'o'的改为'-'
        for (int i = 0; i < board.length; i++) {
            //左
            if (board[i][0] == 'O') {
                bfs2(board, i, 0, '-', 'O');
            }
            //右
            if (board[i][board[0].length - 1] == 'O') {
                bfs2(board, i, board[0].length - 1, '-', 'O');
            }
        }

        for (int i = 1; i < board[0].length - 1; i++) {
            //上
            if (board[0][i] == 'O') {
                bfs2(board, 0, i, '-', 'O');
            }
            //下
            if (board[board.length - 1][i] == 'O') {
                bfs2(board, board.length - 1, i, '-', 'O');
            }
        }
        //第二部，将中间的'o'改为'x'
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                if (board[i][j] == 'O') {
                    bfs2(board, i, j, 'X', 'O');
                }
            }
        }
        //第三步，将边上的'-'改为'o'
        for (int i = 0; i < board.length; i++) {
            //左
            if (board[i][0] == '-') {
                bfs2(board, i, 0, 'O', '-');
            }
            //右
            if (board[i][board[0].length - 1] == '-') {
                bfs2(board, i, board[0].length - 1, 'O', '-');
            }
        }

        for (int i = 1; i < board[0].length - 1; i++) {
            //上
            if (board[0][i] == '-') {
                bfs2(board, 0, i, 'O', '-');
            }
            //下
            if (board[board.length - 1][i] == '-') {
                bfs2(board, board.length - 1, i, 'O', '-');
            }
        }
    }

    public void bfs2(char[][] board, int x, int y, char op, char op1) {
        if (!inArea(board, x, y)) {
            return;
        }

        if (board[x][y] != op1) {
            return;
        }

        board[x][y] = op;

        bfs2(board, x - 1, y, op, op1);
        bfs2(board, x + 1, y, op, op1);
        bfs2(board, x, y + 1, op, op1);
        bfs2(board, x, y - 1, op, op1);
    }

    boolean inArea(char[][] grid, int r, int c) {
        return 0 <= r && r < grid.length
                && 0 <= c && c < grid[0].length;
    }


    /**
     *
     * 827. 最大人工岛
     * 困难
     * 386
     * 相关企业
     * 给你一个大小为 n x n 二进制矩阵 grid 。最多 只能将一格 0 变成 1 。
     * 返回执行此操作后，grid 中最大的岛屿面积是多少？
     * 岛屿 由一组上、下、左、右四个方向相连的 1 形成。
     *
     * 示例 1:
     * 输入: grid = [[1, 0], [0, 1]]
     * 输出: 3
     * 解释: 将一格0变成1，最终连通两个小岛得到面积为 3 的岛屿。
     * 示例 2:
     * 输入: grid = [[1, 1], [1, 0]]
     * 输出: 4
     * 解释: 将一格0变成1，岛屿的面积扩大为 4。
     * 示例 3:
     *
     * 输入: grid = [[1, 1], [1, 1]]
     * 输出: 4
     * 解释: 没有0可以让我们变成1，面积依然为 4。
     *
     *
     * @param grid
     * @return
     */

    public int largestIsland(int[][] grid) {
        int res = 0;
        boolean flag = false;
        int count = 2;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] == 0) {
                    grid[i][j] = 1;
                    res = Math.max(res, bfs3(grid, i, j, count++));
                    grid[i][j] = 0;

                    flag = true;
                }
            }
        }
        if (!flag) {
            return grid.length * grid[0].length;
        }
        return res;
    }




    public int bfs3(int[][] grid, int x, int y, int ops) {
        if (!inArea(grid, x, y)) {
            return 0;
        }


        if (grid[x][y] == 0 || grid[x][y] == ops) {            //遍历过，或者是为0
            return 0;
        }

        //已经遍历过
        grid[x][y] = ops;
        int area =  1 + bfs3(grid, x + 1, y, ops) + bfs3(grid, x - 1, y, ops) +
                bfs3(grid, x, y + 1, ops) + bfs3(grid, x, y - 1, ops);

        return area;
    }


    boolean inArea(int[][] grid, int r, int c) {
        return 0 <= r && r < grid.length
                && 0 <= c && c < grid[0].length;
    }


    /**
     *
     * 841. 钥匙和房间
     * 中等
     * 351
     * 相关企业
     * 有 n 个房间，房间按从 0 到 n - 1 编号。最初，除 0 号房间外的其余所有房间都被锁住。你的目标是进入所有的房间。然而，你不能在没有获得钥匙的时候进入锁住的房间。
     * 当你进入一个房间，你可能会在里面找到一套不同的钥匙，每把钥匙上都有对应的房间号，即表示钥匙可以打开的房间。你可以拿上所有钥匙去解锁其他房间。
     * 给你一个数组 rooms 其中 rooms[i] 是你进入 i 号房间可以获得的钥匙集合。如果能进入 所有 房间返回 true，否则返回 false。
     *
     * 示例 1：
     * 输入：rooms = [[1],[2],[3],[]]
     * 输出：true
     * 解释：
     * 我们从 0 号房间开始，拿到钥匙 1。
     * 之后我们去 1 号房间，拿到钥匙 2。
     * 然后我们去 2 号房间，拿到钥匙 3。
     * 最后我们去了 3 号房间。
     * 由于我们能够进入每个房间，我们返回 true。
     * 示例 2：
     * 输入：rooms = [[1,3],[3,0,1],[2],[0]]
     * 输出：false
     * 解释：我们不能进入 2 号房间。
     * @param rooms
     * @return
     */
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        boolean[] vis = new boolean[rooms.size()];

        bfs4(rooms, vis, 0);

        for (boolean flag : vis) {
            if (!flag) {
                return false;
            }
        }

        return true;

    }


    public void bfs4(List<List<Integer>> rooms, boolean[] vis, int key) {
        if (vis[key]) {     //当前房间访问过
            return;
        }

        //设置当前房间访问过
        vis[key] = true;

        //继续访问下一个房间
        for (Integer id : rooms.get(key)) {
            bfs4(rooms, vis, id);
        }
    }


    /**
     * 463. 岛屿的周长
     * 简单
     * 718
     * 相关企业
     * 给定一个 row x col 的二维网格地图 grid ，其中：grid[i][j] = 1 表示陆地， grid[i][j] = 0 表示水域。
     * 网格中的格子 水平和垂直 方向相连（对角线方向不相连）。整个网格被水完全包围，但其中恰好有一个岛屿（或者说，一个或多个表示陆地的格子相连组成的岛屿）。
     * 岛屿中没有“湖”（“湖” 指水域在岛屿内部且不和岛屿周围的水相连）。格子是边长为 1 的正方形。网格为长方形，且宽度和高度均不超过 100 。计算这个岛屿的周长。
     * @param grid
     * @return
     */
    public int islandPerimeter(int[][] grid) {
        int[] dirx = {-1, 1, 0, 0};
        int[] diry = {0, 0, -1, 1};
        int res = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] == 1) {
                    for (int x = 0; x < 4; x++) {
                        int m = i + dirx[x];
                        int n = j + diry[x];
                        if (m < 0 || m >= grid.length || n < 0 | n >= grid[i].length || grid[m][n] == 0) {
                            res++;
                        }
                    }
                }
            }
        }

        return res;
    }


}

